
/**
 * Author:kongguoguang
 * Date:2020/8/4
 * Time:17:16
 * Summary:
 */
public class BinarySearchUtil {

    public static void main(String[] args) {
        int[] array = {-4, 1, 2, 2, 5, 5, 5, 8, 10};
        int t = 6;
        int index = searchLastLessThanOrEqualElement(array, t);

        if (index == -1){
            System.out.println("can not find any one less than or equal to " + t);
        } else {
            System.out.println("the index of the last one less than or equal to " + t + " is " + index);
        }
    }

    /**
     * 从数组中查找最后一个小于等于给定值的元素
     * @param array 有序整型数组
     * @param t 给定值
     * @return 查找结果元素下标（-1表示没找到）
     */
    private static int searchLastLessThanOrEqualElement(int[] array, int t){
        if (array == null || array.length == 0){
            return -1;
        }
        int length = array.length;
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > t) {
                high = mid - 1;
            } else {
                if ((mid == length - 1) || (array[mid + 1] > t)) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }

        return -1;
    }
}
